/**
 * 剑指 Offer 60. n个骰子的点数
 * https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
 */
const { displayBaseArray } = require('../../libs/public');

const cache = new Map();
cache.set(1, [6, 1, 1, 1, 1, 1, 1]);

/**
 * @param {number} n
 * @return {number[]}
 */
function dichotomy(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  const child1 = dichotomy(n >> 1);
  const child2 = dichotomy(n - (n >> 1));
  const result = new Array(n * 6 + 1);
  let total = 0;
  for (let i = 1; i < child1.length; i += 1) {
    if (!child1[i]) {
      continue;
    }
    for (let j = 1; j < child2.length; j += 1) {
      if (!child2[j]) {
        continue;
      }
      const value = i + j;
      const count = child1[i] * child2[j];
      total += count;
      result[value] = count + (result[value] || 0);
    }
  }
  result[0] = total;
  return result;
}

/**
 * @param {number} n
 * @return {number[]}
 */
function dicesProbability(n) {
  const result = [];
  const counts = dichotomy(n);
  const [total] = counts;
  for (let i = 1; i < counts.length; i += 1) {
    if (counts[i]) {
      result.push(counts[i] / total);
    }
  }
  return result;
}

console.log(displayBaseArray(dicesProbability(1)) === '[0.16666666666666666,0.16666666666666666,0.16666666666666666,0.16666666666666666,0.16666666666666666,0.16666666666666666]');
console.log(displayBaseArray(dicesProbability(2)) === '[0.027777777777777776,0.05555555555555555,0.08333333333333333,0.1111111111111111,0.1388888888888889,0.16666666666666666,0.1388888888888889,0.1111111111111111,0.08333333333333333,0.05555555555555555,0.027777777777777776]');
